package linkedlist;

/**
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，
 * 使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 */
public class no86 {
    public ListNode partition(ListNode head, int x) {
        ListNode beforeBegin = null;
        ListNode beforeEnd = null;
        ListNode afterBegin = null;
        ListNode afterEnd = null;
        if(head == null || head.next == null){
            return head;
        }
        ListNode cur = head;
        while (cur != null){
            if(cur.val < x){
                if(beforeBegin == null){
                    beforeBegin = cur;
                    beforeEnd = cur;
                }else{
                    beforeEnd.next = cur;
                    beforeEnd = beforeEnd.next;
                }
                cur = cur.next;
            }else{
                if(afterBegin == null){
                    afterBegin = cur;
                    afterEnd = cur;
                }else{
                    afterEnd.next = cur;
                    afterEnd = afterEnd.next;
                }
                cur = cur.next;
            }
        }
        if (beforeBegin == null){
            return afterBegin;
        }
        if (afterBegin == null){
            return beforeBegin;
        }
        beforeEnd.next = afterBegin;
        afterEnd.next = null;
        return beforeBegin;
    }
}
